\section{Problema 2}

\subsection{Introducci\'on}
En este problema, dada una red telefónica de localidades unidas por enlaces, debemos encontrar un subconjunto mínimo de enlaces
telefónicos entre localidades tal que en el caso de que alguno de los enlaces no pertenecientes a este subconjunto
fallen, todas las ciudades sigan estando interconectadas. Sabemos que entre dos localidades puede haber uno o más enlaces, y que dichos enlaces  entre las ciudades tienen un costo asociado.\\



	   	
\subsection{Desarrollo}

Para resolverlo decidimos plantear el problema como un problema de grafos. 
Tendremos una red de localidades que ser\'a modelada como un grafo en donde las
localidades ser\'an los nodos  y los enlaces ser\'an las aristas del mismo.\\

Nuestro algoritmo deber\'a entonces encontrar el subconjunto
mínimo de ejes descripto arriba, tal que dado un par cualquiera de localidades de la red, pueda establecerse una comunicación entre ambas. En otras palabras, el algoritmo buscará un árbol generador mínimo del grafo subyacente, que representa la red de localidades. \\
Se decidió implementar el algoritmo de \textbf{Prim} para encontrar un árbol generador mínimo del grafo.\\

Prestando atención al enunciado, sabemos que al poder existir más de un enlace entre dos localidades, el grafo subyacente de la red, podría resultar en un 
\textit{multigrafo} o \textit{pseudografo}. Decidimos resolver este problema, asumiendo que solo tenemos un enlace posible entre dos localidades. En caso de existir más de uno, solo se considera el enlace de menor costo como el enlace entre las localidades involucradas. De esta manera, siempre tenemos un grafo simple como entrada de nuestro algoritmo.\\

Tal como lo describe el algoritmo de \textit{Prim}, nuestra implementación genera el árbol, eligiendo un nodo arbitrariamente al principio. Luego, en cada iteración del algoritmo, se va eligiendo un eje mínimo tal que extienda el árbol sin generar ciclos, es decir, un eje tal que uno de sus nodos pertenezca al árbol que se está generando, y tal que el otro extremo no.\\ 

Se decidió que la representación del grafo sea dada por una matriz de adyacencias. Esta matriz contiene en las posiciones \textit{i,j} el costo asociado al enlace entre las localidades \textit{i} y \textit{j}. Si dos localidades no tienen enlaces entre sí, entonces el valor en esa posición de la matriz será 0.\\
Otras estructuras usadas en el algoritmo, consisten en conjuntos (representados con la clase \textit{HashSet}), o listas (representados por la clase \textit{ArrayList}).

\subsubsection{Aclaraciones}
Se implementaron dos versiones distintas de este problema. El código adjunto posee ambas soluciones, aunque en el caso de la primera no se asegura su funcionamiento.\\

\color{red}
Agregar explicacion de la primera version del ejercicio
\color{black}








\subsection{Pseudoc\'odigo}
El pseudocódigo está compuesto de dos funciones principales: \textit{computeMinimumSpanningTree} y \textit{findMinAdjacentTree}.\\

\begin{itemize}
 
 \item  \textit{computeMinimumSpanningTree}: Esta función contiene un ciclo tal que en cada iteración, busca extender el árbol generado, buscando un nodo no utilizado aún. Esta función usa \textit{findMinAdjacentTree}.
 \item  \textit{findMinAdjacentTree}: Esta función toma un conjunto \textbf{A} de nodos como parámetro. Tal conjunto es un subconjunto de los nodos del grafo. Esta función, busca un eje de costo mínimo, tal que dicho eje es incidente a un nodo que pertenece al conjunto \textbf{A}, pero al mismo tiempo es incidente a otro nodo que no pertenece a \textbf{A}.

\end{itemize}
\begin{parr}
\begin{algorithm}[H]
\caption{\operL{computeMinimumSpanningTree}{}{minimuSpanningTree}}
\begin{algorithmic}[1]\parskip=1mm

\STATE inicializamos el arbol vacio
\STATE minimuSpanningTree $\leftarrow {\O} $ 

\STATE treeLocalities $\leftarrow {\O} $ 

\STATE treeLocalities $\leftarrow$ Agrego un vertice arbitrariamente, por ejemplo el 0

	\WHILE{(Mientras no hayamos cubierto todos los vertices de la red)}
		\STATE buscamos el eje de menor costo, tal que expande el arbol desde los vertices que elegimos, para esto usamos la funcion findMinAdjacentEdge
		\STATE minLInk $\leftarrow$ findMinAdjacentEdge(treeLocalities)

			\IF{(el "primer" vertice del nuevo eje esta en mi arbol, o sea si lo extiende)}
				\STATE Agrego el otro extremo(vertice) a mi arbol(treeLocalities)
			\ELSE
				\STATE Agrego el "primer" vertice a mi arbol(treeLocalities)
			\ENDIF
		\STATE Agregamos el nuevo eje al arbol(treeLocalities)
	\ENDWHILE

\end{algorithmic}
\end{algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{algorithm}[H]
%\caption{\operL{DisctricNetwork}{ \vinout{localities}{List$<$Integer$>$}, \vinout{links}{Link$<$Link$>$}}{}}
%\begin{algorithmic}[1]\parskip=1mm

%\STATE Me creo la matriz de adyacencias de nxn donde n = a la cantidad de localides
%\STATE network $\leftarrow$ int[][]


%\FOR{(i = 0 hasta la cantidad de localidaes, sumando de a 1)}
%	\FOR{(i = 0 hasta la cantidad de localidades, sumando de a 1)}
%		\STATE relleno la matriz de adyacencias con 0
%		\STATE network[i][j] = 0
%	\ENDFOR
%\ENDFOR

%	\WHILE{(Haya mas links para mirar)}
%		\STATE locality $\leftarrow$ peso del eje del link actual.
%		\STATE link $\leftarrow$ el link que estoy mirando en el while.
%		\STATE cost $\leftarrow$ peso del link que estoy mirando.

%		\STATE posLoc1 $\leftarrow$ va a ser la posicion en mi lista localties de uno de los extremos del link que estoy mirando
%		\STATE posLoc2 $\leftarrow$ va a ser la posicion en mi lista localties de uno de los extremos del link que estoy mirando(diferente al de arriba)

%		\IF{(el costo de unir dos ciudades(posLoc1, posLoc2) es mas grande que el costo actual de mi link o simplemente tengo tengo un 0 en esa posicion )}
%			\STATE network[posLoc1][posLoc2] = cost;	le asignamos ese costo al eje que une esas dos localidades
%			\STATE network[posLoc2][posLoc1] = cost;   le asignamos ese costo al eje que une esas dos localidades
%		\ENDIF
%	\ENDWHILE

%\end{algorithmic}
%\end{algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[H]
\caption{\operL{findMinAdjacentEdge}{ \vin{treeLocalties}{Set$<$Integer$>$}}{Link}}
\begin{algorithmic}[1]\parskip=1mm

\STATE minLinkCost $\leftarrow \infty$
\STATE bufferedLocA = 0
\STATE bufferedLocB = 0

	\WHILE{(Haya mas localidades para mirar)}
		\STATE locality $\leftarrow$ peso del eje de la localidad actual.

		\FOR{( cada nodo $j$ del grafo )}
			\IF{(existe el eje $(j,locality)$)}
				\IF{(La localidad es nueva)}
					\IF{(Encontramos un costo menor al que ya teniamos)}
						\STATE minLinkCost $\leftarrow$ localidad actual.
						\STATE bufferedLocA $\leftarrow$ costo de la localidad actual
						\STATE bufferedLocB $\leftarrow$ me guardo el numero de la localidad actual.			
					\ENDIF		
				\ENDIF
			\ENDIF
		\ENDFOR
	\ENDWHILE

\STATE minLink $\leftarrow$ va a ser el nuevo link encontrado, con costo minimo.
\STATE \textbf{return} minLInk

\end{algorithmic}
\end{algorithm}
\end{parr}

\newpage

\subsection{Complejidad}

El algoritmo usa la clase \textit{HashSet} de Java, que nos asegura una complejidad de \textbf{orden constante} para las operaciones de creación, \textit{add()}, \textit{contains()}, \textit{size()}, así como la operación \textit{get()} de \textit{ArrayList}.\\
Para analizar la complejidad de este algoritmo, vamos a calcular el costo temporal de las funciones anteriormente descriptas:\\


\begin{itemize}
 
 \item  $computeMinimumSpanningTree$: Esta función posee un ciclo que itera \textbf{n} veces, siendo \textit{n} la cantidad de nodos del grafo dado.
 Dentro del cuerpo del ciclo, se realizan operaciones constantes sobre conjuntos, y se hace una llamada a \textit{findMinAdjacentTree}. Con lo cual podemos deducir, que el costo temporal de la ejecución de una iteración del ciclo, es igual al costo de \textit{findMinAdjacentTree}, mas otros valores constantes.
 \item  $findMinAdjacentTree$: Esta función toma un conjunto de nodos de un tamaño determinado acotado \textbf{s}, y revisa las adyacencias de esos nodos con otros nodos, buscando un eje mínimo para extender el árbol. Las operaciones realizadas tambien son constantes, pero se revisan como máximo \textbf{s.n} nodos, es decir una constante multiplicada por la cantidad de nodos del grafo, en el peor caso\footnote{Peor caso: un grafo completo $K_n$}. Esto significa que \textit{findMinAdjacentTree}, tiene una complejidad temporal de orden lineal \textbf{n}.\\
\end{itemize}


\begin{center}
    \begin{tabular}{ | p{17cm} |}
	\hline
	\\
 Concluyendo, tenemos que la función $computeMinimumSpanningTree$ ejecuta un ciclo n veces, ejecutando dentro del mismo la función $findMinAdjacentTree$, la cual tiene un costo de orden lineal \textit{n}. Dado esto, podemos concluir que el orden de complejidad del algoritmo es de \textbf{O($n^2$)}, siendo \textit{n} la cantidad de nodos del grafo.
 	\\
	 \\ \hline
    \end{tabular}
\end{center}

Con esto, se cumple lo pedido por la cátedra, es decir, que el tiempo de ejecución del algoritmo se cumpla en \textbf{O($n*m$)}, con \textit{n} nodos y \textit{m} vértices. Esto lo podemos afirmar, ya que el algoritmo devuelve un árbol generador mínimo del grafo, este árbol contiene \textit{n-1} aristas (por propiedad del árbol). Entonces podemos acotar $nm \geq n(n-1) \approx $    \textbf{O($n^2$)}\\

\subsection{Correctitud de la solución}
Para demostrar la correctitud del algoritmo, debemos mostrar que el algoritmo de Prim es correcto y que construye un árbol generador mínimo. \\


%***************************************************************************
%DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO-DEMO
%***************************************************************************

Sea $T_k$ el algoritmo de Prim después de k iteraciones del algoritmo de Prim en un grafo conexo G, para 0 $\leq$ k $\leq$ $|V_G|-1$. Entonces $T_k$ es un sub\'arbol de un \'arbol generador m\'inimo de G.
D//:
La afirmaci\'on es trivialmente verdadera para k = 0 ya que $T_0$ es el \'arbol trivial que consiste del único vértice.
En base a la inducción, asumir para algún k, 0 $\leq$ k $\leq$ $|V_G|-2$ que T$_k$ es un subárbol de un árbol generador mínimo T de G y considerar el árbol T$_{l+1}$. El algoritmo generó a T$_{k+1}$ durante la (k +1)-ésima iteración al agregar un eje frontera \textit{e} a T$_k$  de mínimo peso. Sean \textit{u} y \textit{v} los vértices incididos por e tal que \textit{u} está en T$_k$ y \textit{v} no.
Si el árbol generador T contiene al eje e, entonces T$_{k+1}$ es un subárbol de T. Si e no es un eje en el árbolo T, entnces e es parte de un único ciclo contenido en T+e. Considerar el camino ``más largo'' desde u hasta v en T. En este camino, sea f el primer eje que une un vértice en T$_k$ a un vértice no en T$_k$. La situación está ilustrada en la siguiente ilustración:
\begin{figure}[H]
\centering
\epsfig{file=./graficos/figura-demo-prim-png.pdf,width=0.7\linewidth,clip=}
\caption{Figura para entender mejor demo Prim}
\label{fig:completo}
\end{figure}

Los vértices negros y los ejes en negrita conforman el árbol T$_k$ de Prim. El árbol generador T consiste de todo menos el eje e y el árbol de Prim T$_{k+1}$ = (T$_k$ $\cup$ v)+ e.
Como f era un eje de la frontera en el principio de la (k+1)-ésima iteración, w(e) $\leq$ w(f) (ya que el algoritmo eligió a e). El árbol T$'$ = T+e-f claramente genera a G y T$_{k+1}$ es un subárbol de T$'$ (ya que f no era parte de T$_k$. Finalmente, W(T$'$) = W(T)+w(e)-w(f) $\leq$ W(T) lo que demuestra que T$'$ es un árbol generador mínimo de G.\footnote{Graph Theory And Its aplications. Gross. Yellen. Páginas 177-178}

%%Corolario: Cuando el algoritmo de prim es aplicado a un grafo conexo produce un árbol generador mínimo
%%D//: la proposición anterior implica que el árbol de Prim resultante de la última iteración es un árbol generador mínimo.


\subsection{Casos de Tests}
\textit{Para los tests de rendimiento contamos las operaciones básicas. Es decir, usamos un contador y cada vez que había una operación que tome tiempo constante sumábamos 1 a este contador y para todas las funciones que tarden O(n) con \textit{n} algun entero, sumábamos n al contador, si sólo si no podemos contar atómicamente las n posiciones de esta operación.}

Como el tiempo de nuestra implementación depende mucho de qué tan disperso o denso es un grafo, más allá de las multi aristas, decidimos hacer 2 grupos de tests con 2 subgrupos cada uno:


\begin{compactitem}
	\item \textbf{Test Muchas aristas repetidas (más de 3) entre 2 mismas localidades:} 
	\begin{compactitem}
		\item Grafo denso: más allá de las multi-aristas. Es decir, lo consideramos denso tomando cada multi-arista como un sólo eje.
		\item Grafo disperso: de nuevo ignorando las multi-aristas, un grafo disperso.
		\item Grafo completo: con toda la cantidad posible de aristas de un grafo simple.
	\end{compactitem}
	\item \textbf{Grafo simple:} es decir, no hay multi-aristas
	\begin{compactitem}
		\item Grafo denso.
		\item Grafo disperso.
		\item Grafo completo
	\end{compactitem}
\end{compactitem}

La definición de grafo \textit{denso} o \textit{disperso} no es muy exacta. Por eso, decidimos usar la definición de \textbf{densidad} provista por \texttt{wikipedia}\footnote{http://en.wikipedia.org/wiki/Dense\_graph}:
\begin{center}
    \begin{tabular}{ | p{17cm} |}
	\hline \\
	D = $\frac{2m}{n(n-1)}$
	\begin{compactenum}
		\item Si es un grafo completo, D = 1.
		\item Si es un grafo sin ejes, D = 0.
		\item Si es un grafo conexo (m$\geq$n-1), D $\geq \frac{2}{n}$.
	\end{compactenum}
	 \\ \hline
    \end{tabular}
\end{center}

Si analizamos mejor el caso en el que el grafo es conexo, mientras más grande sea \textit{n} más denso será el árbol con esa cantidad de vértices. Por ende, decidimos hacer tests con grafos con cantidad de vértices mayores o iguales a 7 (la densidad del árbol respectivo a cada n es menor o igual a 0.28 (que sería el caso de n = 7) y disminuye rápidamente. Es más, tiende a ser 0).Dado a que recibiremos un grafo conexo, asumiremos lo siguiente:

\begin{compactitem}
	\item \textbf{Grafo disperso:} 0.30 $\leq$ D $\leq$ 0.50
	\item \textbf{Grafo disperso:} 0.70 $\leq$ D $\leq$ 0.93
\end{compactitem}

\subsection{Gráficos}
NOTA: consideramos como tamaño de entrada a la cantidad de v\'ertices ya que de esta forma es m\'as f\'acil hacer los gr\'aficos en base a n$^2$ en vez del caso en el que usamos al tamaño de entrada como la cantidad de ejes.


\begin{figure}[H]
\centering
\epsfig{file=./graficos/completo-png.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Grafo Completo}
\label{fig:completo}
\end{figure}
En nuestro primer gráfico, analizaremos el rendimiento del algoritmo para los tests del grafo completo repitiendo y sin repetir aristas (o sea, grafo simple versus multi-grafo).
Claramente, el tiempo de ejecuci\'on del algoritmo es m\'as que lineal pero igual lo pudimos acotar con una función cuadr\'atica en base a la cantidad de ciudades. En este caso en particular con la función \texttt{400 * n$^2$}.
Casi no se puede percibir la diferencia entre ejecuciones de ambos tests, pero si se mira con atención el gráfico se puede llegar a notar una pequeña mayor cantidad de ejecuciones por parte del multi-grafo. 
Esto se debe a que nuestro algoritmo antes de empezar a generar el grafo, saca los ejes repetidos y para esto debe iterar la cantidad de ejes de entrada. La cantidad de ejes entre ambos varía, ya que el multi-grafo tiene la misma cantidad de vértices pero más ejes, más del doble si tenemos en cuenta que duplicamos o triplicamos la cantidad de veces que repite cada eje. Por esta variación en la cantidad de ejes, en el grafo simple tiene muchos menos ejes para iterar, lo que significaría una diferencia constante con el multi-grafo que es la pequeña diferencia notable en el gráfico de rendimiento aquí mostrado.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/disperso-png.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Grafo Disperso}
\label{fig:disperso}
\end{figure}

\begin{figure}[H]
\centering
\epsfig{file=./graficos/denso-png.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Grafo Denso}
\label{fig:denso}
\end{figure}
En los casos que quedan ( denso y disperso ambos repitiendo y sin repetir aristas) claramente pasaría lo mismo.
La única diferencia notable es que en el test de completo (el primero) los puntos ``siguen'' una misma función mientras que en los 2 restantes están como más esparcidos en el gráfico. Esto se debe al hecho de que la densidad del completo es siempre la misma (es 1) a diferencia de los tests con disperso y denso, en los que la densidad varía entre 0.3 y 0.5 para el primero; y 0.70 y 0.93 para el segundo.
Sin embargo, en los 3 gráficos pudimos acotar por una función cuadrática el crecimiento del algoritmo.
\textit{Aunque se parezcan mucho los últimos 2 (disperso y denso), notar la diferencia entre las magnitudes del eje \textbf{y} entre ambos}
\subsection{Conclusiones}
En este ejercicio aprendimos a implementar una de las opciones disponibles para encontrar un árbol generador mínimo en un dado grafo, usando el algoritmo de \textit{Prim}. Tambien aprendimos a representar un grafo mediante una matriz de adyacencias. Usando distintas densidades para las matrices de adyacencias subyacentes al problema, pudimos analizar el comportamiento del algoritmo para distintos tipos de grafos.\\





